package insertionSort;

import selectionSort.ArrayGenerator;
import selectionSort.SortingHelper;

public class ReversedInsertionSort {
    /**
     * 作业：反向实现选择排序。
     * @param data
     * @param <E>
     */
    public static <E extends Comparable<E>> void sort(E[] data) {
        //循环不变量：[0,i)未排序，[i,n)已排序
        for (int i = data.length -1; i > 0; i--) {
            int j;
            E tmp = data[i-1];
            for (j = i; j < data.length && (tmp.compareTo(data[j]) > 0); j++)
                data[j - 1] = data[j];
            data[j - 1] = tmp;
        }
    }

    public static void main(String[] args) {
        int n = 1000;
        Integer [] data = ArrayGenerator.generateRandomArray(n,n);
        SortingHelper.sortTest("ReversedInsertionSort",data);
        System.out.println("ReversedInsertionSort ok.");
    }
}
